package org.example.graph_theory;

import java.util.Arrays;

public class The_cheapest_flight_within_K_station {
    public static void main(String[] args) {
        //K 站中转内最便宜的航班

        //有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
        //现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

//        int n = 3;
//        int[][] edges = {{0,1,100},{1,2,100},{0,2,500}};
//        int src = 0, dst = 2, k = 1;
//
//        int n = 5;
//        int[][] edges = {{1,2,10},{2,0,7},{1,3,8},{4,0,10},{3,4,2},{4,2,10},{0,3,3},{3,1,6},{2,4,5}};
//        int src = 0, dst = 4, k = 1;
//
//        int n = 3;
//        int[][] edges = {{0,1,2},{1,2,1},{2,0,10}};
//        int src = 1, dst = 2, k = 1;


        int n = 10;
        int[][] edges = {{0,1,20},{1,2,20},{2,3,30},{3,4,30},{4,5,30},{5,6,30},{6,7,30},{7,8,30},{8,9,30},{0,2,9999},{2,4,9998},{4,7,9997}};
        int src = 0, dst = 9, k = 4;

        int cheapestPrice = findCheapestPrice(n, edges, src, dst, k);
        System.out.println(cheapestPrice);

    }

    //Bellman-ford算法
    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int max = 10000 * 101 + 1;
        int len = k+2;
        int[][] bf = new int[len][n];

        for (int i = 0; i < bf.length; i++) {
            Arrays.fill(bf[i],max);
        }

        bf[0][src] = 0;
        System.out.println(Arrays.toString(bf[0]));
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < flights.length; j++) {
                int from = flights[j][0],to = flights[j][1],price = flights[j][2];
                bf[i][to] = Math.min(Math.min(bf[i-1][to],bf[i-1][from]+price),bf[i][to]);

            }
            System.out.println(Arrays.toString(bf[i]));
        }


        return bf[k+1][dst] == max ? -1 : bf[k+1][dst];
    }
}
